package site.zhouinfo.findpath;

import java.util.ArrayList;


/**
 * A*寻路算法
 *
 * @author zhou
 * @create 2017-10-24 10:55
 * @email zhouinfo@qq.com
 * @blog blog.zhouinfo.site
 */
public class AStarFindPath {

    public static void main(String[] args) {
        NodePointList node = new NodePointList();
        int[][] map = new int[][]{
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},};

        NodePoint start = new NodePoint(4, 3);
        NodePoint end = new NodePoint(5, 7);
/*

        int[][] map = new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}};
        NodePoint start = new NodePoint(1, 0);
        NodePoint end = new NodePoint(1, 2);

*/

        node.setEnd(end);
        start.setG(0);
        node.add(start);
        outer:

        while (node.getSize() != 0) {
            NodePoint nodePoint = node.get();
            for (int x = nodePoint.getX() - 1; x < nodePoint.getX() + 2; x++) {
                if (x < 0 || x >= map[0].length) {
                    continue;
                }
                for (int y = nodePoint.getY() - 1; y < nodePoint.getY() + 2; y++) {
                    if (y < 0 || y >= map[0].length || map[x][y] == 1 || (x == nodePoint.getX() && y == nodePoint.getY())) {
                        continue;
                    }
                    NodePoint n = new NodePoint(x, y);
                    if (isCorner(nodePoint, n, map)) {
                        continue;
                    }
                    if (node.isCloseList(n)) {
                        n = null;
                        continue;
                    }
                    n.setParentNode(nodePoint);
                    n.setG(nodePoint.getG() + 1);
                    if (n.equals(node.getEnd())) {
                        System.out.println("终点找到了");
                        node.getPath(n);
                        ArrayList<NodePoint> path = node.getPath();
                        print(path, map, start, end);
                        break outer;
                    }
                    node.add(n);
                }
            }
        }

    }

    private static void print(ArrayList<NodePoint> list, int[][] map, NodePoint start, NodePoint end) {
        for (NodePoint nodePoint : list) {
            map[nodePoint.getX()][nodePoint.getY()] = 2;
        }
        for (int i = 0; i < map.length; i++) {
            for (int i1 = 0; i1 < map[0].length; i1++) {
                if (map[i][i1] == 0) {
                    System.out.print("\t");
                } else if (start.getX() == i && start.getY() == i1) {
                    System.out.print("s\t");
                } else if (end.getX() == i && end.getY() == i1) {
                    System.out.print("e\t");
                } else {
                    System.out.print(map[i][i1] + "\t");
                }
            }
            System.out.println();
        }
    }

    private static boolean isCorner(NodePoint nodePoint, NodePoint n, int[][] map) {
        if (nodePoint.getX() != n.getX() || n.getY() != nodePoint.getY()) {
            int x = nodePoint.getX() > n.getX() ? nodePoint.getX() : n.getX();
            int y = nodePoint.getY() > n.getY() ? nodePoint.getY() : n.getY();
            for (int i = x - 1; i <= x; i++) {
                for (int i1 = y - 1; i1 <= y; i1++) {
                    if (i > 0 && i1 > 0 && map[i][i1] == 1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

}
